<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 将数组分成两个数组并最小化数组和的差 -->
    <script>
      var minimumDifference = function (nums) {
        let total = nums.reduce((total, item) => total + item, 0)
        let n = nums.length / 2

        let leftArr = nums.slice(0, n)
        let rightArr = nums.slice(n)
        // 根据当前怎么选的feature 去集合setArr里找 选中的数  并求和
        function getSum(feature, setArr) {
          let ret = 0
          // 可能在哪些位会出现1
          for (let i = 0; i < n; i++) {
            // 当前位选了
            if (feature & (1 << i)) {
              ret += setArr[i]
            }
          }
          return ret
        }
        // key 左边1的个数 或者说左边选了几个数  可能0~15个
        // value 选了key对应个数时  可能组成的数字和有哪些
        let leftMap = new Array(n + 1)
        // leftMap[0] = [0];
        // 同理
        let rightMap = new Array(n + 1)
        // rightMap[0] = [0];

        // 获取1的个数
        function getOneNum(num) {
          let ret = 0
          while (num) {
            let tmp = num & -num
            num ^= tmp
            ret++
          }
          return ret
        }
        for (let i = 0; i < 2 ** n; i++) {
          let oneNum = getOneNum(i)
          leftMap[oneNum] = leftMap[oneNum] || []
          rightMap[oneNum] = rightMap[oneNum] || []
          leftMap[oneNum].push(getSum(i, leftArr))
          rightMap[oneNum].push(getSum(i, rightArr))
        }
        let target = total / 2
        // 排个序二分..
        for (let i = 0; i <= n; i++) {
          leftMap[i] = leftMap[i].sort((a, b) => a - b)
          // leftMap[i] = [...new Set(leftMap[i])];
          rightMap[i] = rightMap[i].sort((a, b) => a - b)
          // rightMap[i] = [...new Set(rightMap[i])];
        }
        function findRecent(arr, target) {
          let l = 0
          let r = arr.length - 1
          // 这里本质也是个能力二分..  找到恰好比target大的最小index （满足xxxx的最小index）
          while (l < r) {
            let middle = (l + r) >> 1
            if (arr[middle] == target) {
              return target
            } else if (arr[middle] > target) {
              r = middle
            } else {
              l = middle + 1
            }
          }
          if (l == 0) {
            return arr[l]
          }
          let left = Math.abs(arr[l - 1] - target)
          let right = Math.abs(arr[l] - target)
          if (left < right) {
            return arr[l - 1]
          } else {
            return arr[l]
          }
        }
        let ret = Infinity
        // 左边拿i个数
        for (let i = 0; i <= n; i++) {
          // 这时候题就变成找波谷了.. 你理解一下  可能有点突兀  当然也可能没波谷 那就找最低点
          for (let j = 0; j < leftMap[i].length; j++) {
            let now = leftMap[i][j]
            // 二分找最理想的那个值
            now += findRecent(rightMap[n - i], target - now)
            let other = total - now
            ret = Math.min(ret, Math.abs(now - other))
          }
        }
        return ret
      }
      console.log(minimumDifference([3, 9, 7, 3]))
    </script>
  </body>
</html>
